package com.tys.algorithm.advanced.code.class20;

/**
 * 最长回文子序列长度
 * 给定一个字符串str，返回这个字符串的最长回文子序列长度
 * 比如：str="a12b3c43def2ghi1kpm"
 * 最长回文子序列是1234321或者123c321或123321，返回长度7
 * <p>
 * 测试链接：https://leetcode.com/problems/longest-palindromic-subsequence/
 */
public class Code01_PalindromeSubsequence {

    //方法1：会超时，慢算不完
    public static int lpsl1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        return f(str, 0, str.length - 1);
    }

    // str[L..R]最长回文子序列长度返回
    public static int f(char[] str, int L, int R) {
        //只有一个字符：最长回文长度，返回1
        if (L == R) {
            return 1;
        }
        //剩2个字符
        //ab 最长 1
        //aa 最长 2
        if (L == R - 1) {
            return str[L] == str[R] ? 2 : 1;
        }
        //可能性1：不以L开头，不以R结尾：a12321b
        int p1 = f(str, L + 1, R - 1);
        //可能性2：以L开头，不以R结尾：12a321b
        int p2 = f(str, L, R - 1);
        //可能性3：不以L开头，以R结尾：a123b21
        int p3 = f(str, L + 1, R);
        //可能性4：以L开头，以R结尾：12321
        //L 和 R 位置字符必须相等：L和R中间的最大回文长度+2(L和R)
        int p4 = str[L] != str[R] ? 0 : (2 + f(str, L + 1, R - 1));
        return Math.max(Math.max(p1, p2), Math.max(p3, p4));
    }

    //方法2：改动态规划
    public static int lpsl2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        //L 0...N-1
        //R 0...N-1
        int[][] dp = new int[N][N];
        //最后字符填1：方便下面一次填2个格子
        dp[N - 1][N - 1] = 1;
        //遍历设置对角线
        for (int i = 0; i < N - 1; i++) {
            //对角线为1
            dp[i][i] = 1;
            //2个字符情况：相邻相等就是2，不相等就是1
            dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
        }
        //L：从下向上填，N-1和N-2都填完了，从N-3出发
        for (int L = N - 3; L >= 0; L--) {
            //R：从L+2开始，之前都已经填了
            for (int R = L + 2; R < N; R++) {

                /**
                 * int p1 = dp[L + 1][R - 1];
                 * int p2 = dp[L][R - 1];
                 * int p3 = dp[L + 1][R];
                 * int p4 = str[L] != str[R] ? 0 : (2 + dp[L + 1][R - 1]);
                 * dp[L][R] = Math.max(Math.max(p1, p2),  Math.max(p3, p4));
                 */
                //优化：不管左下
                //p1和p3进行pk取最大
                dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
                //有p4 情况
                if (str[L] == str[R]) {
                    //和p4进行PK，取最大
                    dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
                }
            }
        }
        //暴力过程返回0...N-1
        return dp[0][N - 1];
    }

    public static int longestPalindromeSubseq1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        char[] str = s.toCharArray();
        char[] reverse = reverse(str);
        return longestCommonSubsequence(str, reverse);
    }

    public static char[] reverse(char[] str) {
        int N = str.length;
        char[] reverse = new char[str.length];
        for (int i = 0; i < str.length; i++) {
            reverse[--N] = str[i];
        }
        return reverse;
    }

    public static int longestCommonSubsequence(char[] str1, char[] str2) {
        int N = str1.length;
        int M = str2.length;
        int[][] dp = new int[N][M];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 1; i < N; i++) {
            dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
        }
        for (int j = 1; j < M; j++) {
            dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (str1[i] == str2[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[N - 1][M - 1];
    }

    public static int longestPalindromeSubseq2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int[][] dp = new int[N][N];
        dp[N - 1][N - 1] = 1;
        for (int i = 0; i < N - 1; i++) {
            dp[i][i] = 1;
            dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
        }
        for (int i = N - 3; i >= 0; i--) {
            for (int j = i + 2; j < N; j++) {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                if (str[i] == str[j]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
                }
            }
        }
        return dp[0][N - 1];
    }

}
